/*
 * @author: wizardc
 */

using System;
using System.Collections.Generic;

namespace Dou.DataStructure
{
    /// <summary>
    /// 二叉堆
    /// 高效获取一堆对象中的最大值或最小值
    /// </summary>
    public class BinaryHeaps<T>
    {
        private List<T> _data;
        private Func<T, T, float> _compare;

        public BinaryHeaps(Func<T, T, float> compare)
        {
            _data = new List<T>();
            _compare = compare;
        }
        
        public List<T> data => _data;
        public int count => _data.Count;
        
        /// <summary>
        /// 添加一个对象
        /// </summary>
        public void Enqueue(T obj)
        {
            _data.Add(obj);
            var parentIndex = (_data.Count - 2) >> 1;
            var objIndex = _data.Count - 1;
            var temp = _data[objIndex];
            while (objIndex > 0)
            {
                if (_compare(temp, _data[parentIndex]) > 0)
                {
                    _data[objIndex] = _data[parentIndex];
                    objIndex = parentIndex;
                    parentIndex = (parentIndex - 1) >> 1;
                }
                else
                {
                    break;
                }
            }
            _data[objIndex] = temp;
        }
        
        /// <summary>
        /// 修改一个对象
        /// </summary>
        public bool Modify(T oldObj, T newObj)
        {
            var objIndex = _data.IndexOf(oldObj);
            if (objIndex == -1)
            {
                return false;
            }
            _data[objIndex] = newObj;
            var parentIndex = (objIndex - 1) >> 1;
            var temp = _data[objIndex];
            while (objIndex > 0)
            {
                if (_compare(temp, _data[parentIndex]) > 0)
                {
                    _data[objIndex] = _data[parentIndex];
                    objIndex = parentIndex;
                    parentIndex = (parentIndex - 1) >> 1;
                }
                else
                {
                    break;
                }
            }
            _data[objIndex] = temp;
            return true;
        }
        
        /// <summary>
        /// 仅获取最大值或最小值，不取出该值
        /// </summary>
        public T Peek()
        {
            if (_data.Count == 0)
            {
                throw new Exception("二叉堆没有数据！");
            }
            return _data[0];
        }
        
        /// <summary>
        /// 取出最大值或最小值
        /// </summary>
        public T Dequeue()
        {
            if (_data.Count == 0)
            {
                throw new Exception("二叉堆没有数据！");
            }
            if (_data.Count == 1)
            {
                var r = _data[0];
                _data.Clear();
                return r;
            }
            var result = _data[0];
            _data[0] = _data[_data.Count - 1];
            _data.RemoveAt(_data.Count - 1);
            var parentIndex = 0;
            var childIndex = 1;
            var temp = _data[parentIndex];
            while (childIndex <= _data.Count - 1)
            {
                if (_data[childIndex + 1] != null && _compare(_data[childIndex], _data[childIndex + 1]) < 0)
                {
                    childIndex++;
                }
                if (_compare(temp, _data[childIndex]) < 0)
                {
                    _data[parentIndex] = _data[childIndex];
                    parentIndex = childIndex;
                    childIndex = (childIndex << 1) + 1;
                }
                else
                {
                    break;
                }
            }
            _data[parentIndex] = temp;
            return result;
        }
        
        public void Clear()
        {
            _data.Clear();
        }
    }
}
